1. Technical Field
The present invention relates to quantum computing and, more particularly, to systems, methods and devices for preparing quantum states.
2. Description of the Related Art
Rejection sampling is a technique for producing samples from a target distribution by starting from samples from another distribution. The method has first been formalized by von Neumann (1951) and has many applications in classical computing. The classical rejection method solves the following resampling problem: given the ability to sample according to some probability distribution p, produce samples from some other distribution q. The method works as follows: let γ≦1 be the largest scaling factor such that γq lies under p, formally, γ=mink(pk/qk). A sample k is accepted from p with probability γqk/pk, otherwise the sample is rejected and the process is repeated. The expected number of samples from p to produce one sample from q is then given by T=1/γ=maxk(qk/pk), which has been proved to be optimal. FIG. 11 provides a visualization of this sampling method. In particular, FIG. 11 is a graph 1100 of Probability v. Sample space (denoted by variable k), where curve 1102 is an example of pk and curve 1104 is an example of γqk. As indicated above,
      Prob    ⁡          (              accept        ⁢                                  ⁢        k            )        =                    γ        ⁢                                  ⁢                  q          k                            p        k              .  
This technique is at the core of many sampling algorithms and has therefore numerous applications, in particular, in the field of Monte Carlo simulations, the most well-known example being the Metropolis algorithm. It is used extensively in Monte Carlo simulations since the simulations seek to sample from distributions that are defined on some extremely high-dimensional spaces and for which sometimes no direct way of sampling is known. Rejection sampling then permits sampling from the target distribution, provided that another, much easier to obtain, distribution can be sampled from.